/**
 * @Question.Title: 矩形区域不超过 K 的最大数值和
 * @Question.No: 363
 * @Author: DQ
 * @Date: 2021-04-22 09:30:21
 * @Description: 
 */
//给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。 
//
// 题目数据保证总会存在一个数值和不超过 k 的矩形区域。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,0,1],[0,-2,3]], k = 2
//输出：2
//解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[2,2,-1]], k = 3
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -100 <= matrix[i][j] <= 100 
// -105 <= k <= 105 
// 
//
// 
//
// 进阶：如果行数远大于列数，该如何设计解决方案？ 
// Related Topics 队列 二分查找 动态规划 
// 👍 201 👎 0

package dq.leetcode.editor.cn;

import com.dq.utils.CreateArray;

import java.util.Arrays;
import java.util.TreeSet;

public class MaxSumOfRectangleNoLargerThanK {
    public static void main(String[] args) {
        Solution solution = new MaxSumOfRectangleNoLargerThanK().new Solution();
        int[][] matrix = (int[][])CreateArray.genIntArray("[[2,2,-1]]");
        int k = 3;
        int res = solution.maxSumSubmatrix(matrix, k);
        System.out.println(res);
    }
        //leetcode submit region begin(Prohibit modification and deletion)

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        matrix = getPreSum(matrix);
        TreeSet<Integer> set = new TreeSet<>();
        int ans = Integer.MIN_VALUE;
        //上边界
        for(int top = 1; top < matrix.length; top++){
            //下边界
            for(int bot = top; bot < matrix.length; bot++){

                set.clear();
                set.add(0);
                for(int j = 1; j < matrix[0].length; j++){
                    int right = matrix[bot][j] - matrix[top-1][j];
                    Integer left = set.ceiling(right - k);
                    if(left != null){
                        ans = Math.max(ans, right - left);
                    }
                    set.add(right);
                }
            }
        }
        return ans;
    }
    //I>0, J>0
    public int getSum(int i, int j, int m, int n, int[][] preSum){
        return preSum[m][n] - preSum[m][j-1] - preSum[i-1][n] + preSum[i-1][j-1];
    }
    public int[][] getPreSum(int[][] matrix){
        int[][] preSum = new int[matrix.length+1][matrix[0].length+1];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++){
                preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] - preSum[i][j] + matrix[i][j];
            }
        }

        return preSum;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}